/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-06-21
 * Time: 10:53
 */
class Solution13 {

    int ret;
    boolean[] check;

    public int countArrangement(int n) {
        check = new boolean[n + 1];

        dfs(1,n);

        return ret;
    }

    void dfs(int pos, int n) {
        if(pos == n+1) {
            ret++;
            return;
        }

        for(int i = 1; i <= n; i++) {
            if(check[i] == false && (i % pos == 0 || pos % i == 0)) {
                check[i] = true;
                dfs(pos+1,n);
                check[i] = false;
            }
        }
    }
}
